/**
 * @param {number} n
 * @param {number} k
 * @param {number} target
 * @return {number}
 */
var numRollsToTarget = function (n, k, target) {
  if (target < n || target > n * k) return 0
  let res = 0, MOD = 10 ** 9 + 7
  let memo = new Array(n+1).fill(-1).map(()=>new Array(target-n+1).fill(-1))
  function dfs(i, j) {
  
    if (i == 0) return j == 0 ? 1 : 0
    for (let x = 0; x < k&&x<=j; x++) {
      res = (res + dfs(i - 1, j - x)) % MOD
    }
    return res
  }

  return dfs(n, target-n)
};